package lcof;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: CuttingRope14I
 * @description: 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。
 * 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/215:38
 * @since V1.0
 */
public class CuttingRope14I {

    /**
     * 这题用动态规划是比较好理解的
     *
     *     我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来
     *     用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1
     *     我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
     *     剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])
     *     第一段长度j可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为
     *     dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
     *     最后返回dp[n]即可
     *
     * 代码
     *
     * 作者：edelweisskoko
     * 链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/jian-zhi-offer-14-i-jian-sheng-zi-huan-s-xopj/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    //动态规划
    public int cuttingRope(int n) {
        //定义dp数组
        int[] dp = new int[n + 1];
        dp[2] = 1;
        //从i开始计算每个dp[i]的大小，一直到 n
        for (int i=3;i<=n;i++){
            //j表示每次剪绳子的长度，从2开始剪才有效
            for (int j=2;j<i;j++){
                //比如此时绳子长为5，从2，3，4分别剪，比较得到dp[5]的最大值
                dp[i] = Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));
            }
        }
        return dp[n];
    }

    /**
     *
     思路二：贪心

     核心思路是：尽可能把绳子分成长度为3的小段，这样乘积最大

     步骤如下：

     如果 n == 2，返回1，如果 n == 3，返回2，两个可以合并成n小于4的时候返回n - 1
     如果 n == 4，返回4
     如果 n > 4，分成尽可能多的长度为3的小段，每次循环长度n减去3，乘积res乘以3；最后返回时乘以小于等于4的最后一小段
     以上2和3可以合并

     作者：edelweisskoko
     链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/jian-zhi-offer-14-i-jian-sheng-zi-huan-s-xopj/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    //贪心算法，绳子按照3来分割的时候最大
    public int 贪心算法(int n){
        if (n<4){
            return n-1;
        }
        //当n从5开始时
        int a =  n/3;
        int b = n%3;
        //当 b=0 时，直接返回 3^a；
        //当 b=1 时，要将一个 1+3 转换为 2+2 因此返回3^{a-1} ×4；
        //当 b=2 时，返回 3^a×2。
        if (b==0) return (int) (Math.pow(3,a));
        if (b==1) return (int) (Math.pow(3,a-1)*4);
        return (int) (Math.pow(3,a)*2);
    }
}
